# -*- coding: utf-8 -*-

"""
    Time    : 2020/11/24 下午6:54
    Author  : Thinkgamer
    File    : 002-两数相加.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/add-two-numbers/
"""

"""
给出两个非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0开头。

示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807


[9,9,9,9,9,9,9]
[9,9,9,9]
"""


# Definition for singly-linked list.
class ListNode(object):
	def __init__(self, val=0, next=None):
		self.val = val
		self.next = next


class Solution(object):
	# 84 ms 14.34% 13.2M 9.68%
	@staticmethod
	def addTwoNumbers(l1, l2):
		"""
		:type l1: ListNode
		:type l2: ListNode
		:rtype: ListNode
		"""
		is_jinwei = 0
		new_list = ListNode()

		# 判断首位是否需要进位
		count = l1.val + l2.val
		if count >= 10:
			is_jinwei = 1
			new_list.val = count - 10
		else:
			new_list.val = count

		# 创建临时遍历，用于链表计算的遍历
		other = new_list
		l1 = l1.next
		l2 = l2.next

		while l1 and l2:
			count = l1.val + l2.val + is_jinwei
			if count >= 10:
				is_jinwei = 1
				temp = ListNode(count-10)
			else:
				is_jinwei = 0
				temp = ListNode(count)
			other.next = temp
			other = temp

			l1 = l1.next
			l2 = l2.next

		# 如果l1 和 l2 还有剩余位，进行拼接
		while l1:
			count = l1.val + is_jinwei
			if count >= 10:
				is_jinwei = 1
				temp = ListNode(count-10)
			else:
				is_jinwei = 0
				temp = ListNode(count)
			other.next = temp
			other = temp

			l1 = l1.next

		while l2:
			count = l2.val + is_jinwei
			if count >= 10:
				is_jinwei = 1
				temp = ListNode(count-10)
			else:
				is_jinwei = 0
				temp = ListNode(count)
			other.next = temp
			other = temp

			l2 = l2.next

		if is_jinwei:
			temp = ListNode(is_jinwei)
			other.next = temp
			other = temp

		show_list(new_list)
		return new_list


	# 68ms 51.61% 13.2m 9.68%
	@staticmethod
	def addTwoNumbers_v2(l1, l2):
		"""
		:type l1: ListNode
		:type l2: ListNode
		:rtype: ListNode
		"""
		isJinwei = 0
		new_list = ListNode()

		# 进行首位的判断
		count = l1.val + l2.val
		if count >= 10:
			isJinwei = 1
			new_list.val = count - 10
		else:
			new_list.val = count
		other = new_list

		l1 = l1.next
		l2 = l2.next

		while l1 and l2:
			count = l1.val + l2.val + isJinwei
			if count >= 10:
				temp = ListNode(count - 10)
				other.next = temp
				other = temp
				isJinwei = 1
			else:
				temp = ListNode(count)
				other.next = temp
				other = temp
				isJinwei = 0
			l1 = l1.next
			l2 = l2.next
		if l1 is None or l2 is None:
			while l1:
				count = l1.val + isJinwei
				isJinwei = count // 10
				temp = ListNode(count % 10)
				other.next = temp
				other = temp
				l1 = l1.next
			while l2:
				count = l2.val + isJinwei
				isJinwei = count // 10
				temp = ListNode(count % 10)
				other.next = temp
				other = temp
				l2 = l2.next
			if isJinwei:
				temp = ListNode(isJinwei)
				other.next = temp
				other = temp
		show_list(new_list)
		return new_list

	@staticmethod
	def addTwoNumbers_v3(l1, l2):
		"""
		:type l1: ListNode
		:type l2: ListNode
		:rtype: ListNode
		"""
		isJinwei = 0
		new_list = ListNode()

		# 进行首位的判断
		count = l1.val + l2.val
		if count >= 10:
			isJinwei = 1
			new_list.val = count - 10
		else:
			new_list.val = count
		other = new_list

		l1 = l1.next
		l2 = l2.next

		while l1 and l2:
			count = l1.val + l2.val + isJinwei
			if count >= 10:
				temp = ListNode(count - 10)
				other.next = temp
				other = temp
				isJinwei = 1
			else:
				temp = ListNode(count)
				other.next = temp
				other = temp
				isJinwei = 0
			l1 = l1.next
			l2 = l2.next
		if l1 is None or l2 is None:
			while l1:
				count = l1.val + isJinwei
				isJinwei = count // 10
				temp = ListNode(count % 10)
				other.next = temp
				other = temp
				l1 = l1.next
			while l2:
				count = l2.val + isJinwei
				isJinwei = count // 10
				temp = ListNode(count % 10)
				other.next = temp
				other = temp
				l2 = l2.next
			if isJinwei:
				temp = ListNode(isJinwei)
				other.next = temp
				other = temp
		show_list(new_list)
		return new_list


def show_list(_list):
	while _list:
		print(_list.val, end=" ")
		_list = _list.next
	print("\n ------------ end !")


def arr_to_list(arr):
	# 创建根结点，指向arr的第一个元素
	root = ListNode(arr[0])
	# 创建一个临时节点，用来进行链表的构建
	other = root
	# 遍历剩下的值
	for one in arr[1:]:
		temp = ListNode(one)
		other.next = temp
		other = temp
	return root


if __name__ == "__main__":
	l1 = arr_to_list([2, 4, 3])
	# l1 = arr_to_list([9,9,9,9,9,9,9])
	# l1 = arr_to_list([9, 9, 1])
	show_list(l1)
	l2 = arr_to_list([5, 6, 4])
	# l2 = arr_to_list([9,9,9,9])
	# l2 = arr_to_list([1])
	show_list(l2)
	s = Solution()
	s.addTwoNumbers(l1, l2)


